Dat je niz pozitivnih celih brojeva. Potrebno je odrediti rastući podniz datog niza čiji je zbir najveći mogući. Program treba da izračuna i ispiše taj maksimalni zbir. Zadatak je dozvoljeno rešiti u proizvoljnoj vremenskoj složenosti. Prostorna složenost mora biti O(n).
Na standardni ulaz unosi se broj n ∈ [1,30]. Nakon toga se unosi n brojeva, svaki iz intervala [0,100000].
Na standardni izlaz ispisati najveći mogući zbir nekog rastućeg podniza datog niza.
8
3 10 2 1 20 4 5 2558